package data_structures_and_algorithms.binary_search.basic;

import java.time.LocalDateTime;
import java.util.Arrays;

/**
 * @ClassName Example01
 * @Description: TODO
 * @Author: yongliang.ma
 * @Create_time:2022/10/25 11:02
 */
public class Example01 {
    // 有序数组中找到num
    static class Search01{
        public static int searchTargetNum(int[] nums, int target){
            int left = 0, right = nums.length - 1;
            while (left < right){
                int mid = (left + right)/2;// 这种写法有问题，可以改善
                if (nums[mid] < target){
                    // 说明target落在mid右边,所以移动left位置
                    left = mid + 1;
                }else if (nums[mid] > target){
                    // 说明target落在mid左边，所以移动right位置
                    right = mid - 1;
                }else {
                    return mid;
                }
            }
            return -1;// 找不到该数字返回-1
        }
        // 改进：防止大数溢出，加差值 使用位运算
        public static int searchTargetNum1(int[] nums, int target){
            int L = 0, R = nums.length - 1;
            while (L < R){
                int mid = L + ((R - L) >> 1);// 防止数字溢出，且使用位运算
                if (nums[mid] < target){
                    // 说明target落在mid右边,所以移动left位置
                    L = mid + 1;
                }else if (nums[mid] > target){
                    // 说明target落在mid左边，所以移动right位置
                    R = mid - 1;
                }else {
                    return mid;
                }
            }
            return -1;// 找不到该数字返回-1
        }

        public static void main(String[] args) {
            int[] nums = new int[]{1,2,3,4,7,9,12,34,56};
            System.out.println(searchTargetNum1(nums, 33));
        }
    }

    // 有序数组中找到>=num最左位置
    static class Search02{
        public static int searchTargetNumIndex(int[] nums, int target){
            int L = 0, R = nums.length - 1, ans = -1;
            while (L <= R){
                int mid = L + ((R - L) >> 1);
                // 思考一下和上面的有所不同
                if (nums[mid] >= target){
                    ans = mid;
                    R = mid - 1;
                }else {// nums[mid] < target
                    L = mid + 1;
                }
            }
            return ans;
        }
    }

    // 有序数组中找到<=num最右位置
    static class Search03{
        public static int searchTargetNumIndex(int[] nums, int target){
            int L = 0, R = nums.length - 1, ans = -1;
            while (L <= R){
                int mid = L + ((R - L) >> 1);
                if (nums[mid] <= target){
                    ans = mid;
                    L = mid + 1;
                }else {// nums[mid] > target，不更新ans
                    R = mid - 1;
                }
            }
            return ans;
        }
    }

    // 局部最小值问题
    static class Search04{
        /**
         * 给你一个无序序列，找到其中一个局部最小值
         *
         * 定义局部最小的概念。arr长度为1时，arr[0]是局部最小。
         * arr的长度为N(N>1)时，如果arr[0]<arr[1]，那么arr[0]是局部最小；
         * 如果arr[N-1]<arr[N-2]，那么arr[N-1]是局部最小；
         * 如果0<i<N-1，既有arr[i]<arr[i-1]又有arr[i]<arr[i+1]，那么arr[i]是局部最小。
         * 给定无序数组arr，已知arr中任意两个相邻的数都不相等，写一个函数，只需返回arr中任意一个局部最小出现的位置即可。
         *
         * 局部最小值得概念：如果一个数字满足比她的左边和右边都小，那么该数字被称为局部最小值
         */

        public static int getMinValLocal(int[] nums){
            if (nums.length == 0)
                return -1;
            if (nums.length == 1)
                return 0;
            if (nums[0] < nums[1])
                return 0;
            if (nums[nums.length - 1] < nums[nums.length - 2])
                return nums.length - 1;
            // 取两头的次位置，可能包含在结果之中
            int L = 1, R = nums.length - 2, mid = -1, ans = -1;
            while (L <= R){// 这里的L <= R 需要注意
                mid = L + ((R - L)>>1);
                if (nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1]){
                    ans = mid;
                    break;
                }
                if (nums[mid] > nums[mid - 1]){
                    R = mid - 1;
                    continue;
                }
                L = mid + 1;
            }
            return ans;
        }

        public static int[] getRandomArray(int maxLen, int maxVal){
            int LENGTH = (int)(Math.random() * (maxLen-1)) + 1;
            int[] arr = new int[LENGTH];
            if (LENGTH > 1){
                arr[0] = (int)(Math.random() * maxVal);
                for (int i = 1; i < LENGTH; i++) {
                    do {
                        arr[i] = (int)(Math.random() * maxVal);
                    }while (arr[i] == arr[i - 1]);// 看起来更加自然  简洁一些
                }
            }else {
                arr[0] = (int)(Math.random() * maxVal);
            }
            return arr;
        }

        public static boolean checker(int[] nums, int index){
            if (nums.length == 0)
                return index == -1;
            boolean lessThanLeft = index - 1 >= 0?nums[index] < nums[index - 1] : true;
            boolean lessThanRight = index + 1 < nums.length?nums[index] < nums[index + 1] : true;
            return lessThanLeft && lessThanRight;
        }

        public static void main(String[] args) {
            int times = 10;
            int maxLen = 10;
            int maxVal = 10;
            for (int i = 0; i < times; i++) {
                int[] randomArray = getRandomArray(maxLen, maxVal);
                int minValLocal = getMinValLocal(randomArray);
                if (!checker(randomArray, minValLocal)){
                    System.out.println("Array error " + Arrays.toString(randomArray));
                    break;
                }
            }
        }
    }
}
